1. Field of the Invention
This invention relates in general to the field of instruction execution in computers, and more particularly to an apparatus and method for executing a forward branch instruction in a pipeline microprocessor.
2. Description of the Related Art
An application program for execution on a microprocessor consists of a structured series of macro instructions that are stored in sequential locations in memory. A current instruction pointer within the microprocessor points to the address of the instruction currently being executed and a next instruction pointer within the microprocessor points to the address of the next instruction for execution. During each clock cycle, the length of the current instruction is added to the contents of the current instruction pointer to form a pointer to a next sequential instruction in memory. The pointer to the next sequential instruction is provided to logic that updates the next instruction pointer. If the logic determines that the next sequential instruction is indeed required for execution, then the next instruction pointer is updated with the pointer to the next sequential instruction in memory. Thus, macro instructions are fetched from memory in sequence for execution by the microprocessor.
Obviously, because a microprocessor is designed to execute instructions from memory in the sequence that they are stored, it follows that a program configured to execute macro instructions sequentially from memory is one which will run efficiently on the microprocessor. For this reason, most application programs are designed to minimize the number of instances where macro instructions are executed out of sequence. These out-of-sequence instances are known as jumps, or branches.
A program branch presents a problem because most conventional microprocessors do not simply execute one instruction at a time. Rather, a present day microprocessor consists of a number of pipeline stages, each stage performing a specific function. Instructions, inputs, and results from one stage to the next are passed in synchronization with a pipeline clock. Hence, several instructions may be executing in different stages of the microprocessor pipeline within the same clock cycle. As a result, when logic within a given stage determines that a program branch is to occur, then previous stages of the pipeline, that is, stages that are executing instructions following in sequence, must be cast out to begin execution of sequential macro instructions beginning with the instruction directed by the branch, or the branch target instruction. This casting out of previous pipeline stages is known as flushing and refilling the pipeline.
Additionally, a microprocessor maintains a number of sequential macro instructions queued up for decode in an instruction buffer, so that a macro instruction is provided each clock cycle for execution. When a program branch is encountered, the contents of the instruction buffer must also be flushed and refilled.
A conditional branch is a branch that may or may not occur, depending upon the evaluation of some specified condition. And, this evaluation is typically performed in later stages of the microprocessor pipeline. To preclude wasting many clock cycles associated with flushing and refilling the pipeline, present day microprocessors also provide logic in an early pipeline stage that predicts whether a conditional branch will occur or not. If it is predicted that a conditional branch will occur, then only those instructions prior to the early pipeline stage must be flushed, including those in the instruction buffer. Even so, this is a drastic improvement; correctly predicted branches are executed in roughly two clock cycles rather than many more.
Yet, present day branch prediction techniques do not consider the contents of the instruction buffer, because the branch prediction typically occurs in a pipeline stage that follows the instruction buffer. In fact, even if the target instruction for the branch is already present in the instruction buffer, the instruction buffer is still flushed and refilled. Thus, the target instruction is fetched again and placed in the buffer.
It has been observed that a notable percentage of conditional branch instructions in application programs branch forward in sequence by only a few instructions. Consequently, when these programs execute on a conventional microprocessor, a significant number of clock cycles are wasted flushing and refilling the instruction buffer with virtually the same contents. When branch prediction logic declares that a conditional branch will be taken, it is very likely that the branch target instruction is already in the instruction buffer.
Therefore, what is needed is a microprocessor that executes a forward branch much faster than has heretofore been provided.
In addition, what is needed is an apparatus in a microprocessor that determines if a branch target instruction is already within its instruction buffer when a branch is declared.
Furthermore, what is needed is a microprocessor that shifts a branch target instruction to the front of the instruction buffer when a conditional branch is declared rather than flushing the buffer and fetching the branch target instruction again.
Moreover, what is needed is a method for executing a forward branch in a microprocessor that determines if a branch target instruction is present in an instruction buffer and, if so, shifts it to the front of the buffer.